package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author 覃国强
 * @date 2021-04-19 22:06
 */
public class 面试题_17_17_多次搜索 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String big = "mississippi";
    String[] smalls = {"is","ppi","hi","sis","i","ssippi"};
    int[][] multiSearch = solution.multiSearch(big, smalls);
    for (int[] arr : multiSearch) {
      System.out.println(Arrays.toString(arr));
    }
  }


  static
  class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
      TrieNode root = TrieNode.generateTrie(smalls);
      char[] chars = big.toCharArray();
      Map<String, Set<Integer>> map = new HashMap<>();

      for (int i = 0; i < chars.length; ++i) {
        int index = i;
        TrieNode tmp = root;
        while (index < chars.length && tmp.children.containsKey(chars[index])) {
          tmp = tmp.children.get(chars[index]);
          if (tmp.end) {
            map.computeIfAbsent(tmp.value, s -> new TreeSet<>());
            map.get(tmp.value).add(index - tmp.value.length() + 1);
          }
          ++index;
        }
      }

      int[][] result = new int[smalls.length][0];

      for (int i = 0; i < smalls.length; ++i) {
        if (map.containsKey(smalls[i])) {
          Set<Integer> set = map.get(smalls[i]);
          int[] arr = new int[set.size()];
          int index = 0;
          for (int position : set) {
            arr[index++] = position;
          }
          result[i] = arr;
        }
      }

      return result;
    }


    static class TrieNode {

      boolean end;

      String value = "";

      Map<Character, TrieNode> children = new HashMap<>();

      public static TrieNode generateTrie(String[] smalls) {
        TrieNode root = new TrieNode();
        for (String word : smalls) {
          TrieNode tmp = root;
          for (char ch : word.toCharArray()) {
            if (!tmp.children.containsKey(ch)) {
              TrieNode node = new TrieNode();
              node.value = tmp.value + ch;
              tmp.children.put(ch, node);
            }
            tmp = tmp.children.get(ch);
          }
          tmp.end = true;
        }
        return root;
      }
    }
  }

}
